// 22. 括号生成
/**
 * @param {number} n
 * @return {string[]}
 */

// 深度优先搜索
var generateParenthesis = function (n) {
    const res = []
    const dfs = (str, left, right) => {
        // 去除无效的括号组合
        // 左括号不能过半
        // 右括号不能超过左括号，因为右括号不能在对应的左括号出现
        if (left > n || right > left) return
        if (str.length === 2 * n) {
            return res.push(str)
        }
        // 下一个追加左括号，左括号数量+1
        dfs(`${str}(`, left + 1, right)
        // 右括号数量+1
        dfs(`${str})`, left, right + 1)
    }

    dfs("", 0, 0)
    return res
};


const result = generateParenthesis(2)
console.log("result :>>", result);